# coding=utf-8
__author__ = 'st316'
'''
Given a string S, find the longest palindromic substring in S.
You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.
'''


class Solution:
    # @return a string
    def longestPalindrome(self, s):
        T = self.preProcess(s)
        n = len(T)
        P = [0 for i in xrange(n)]
        C = 0
        R = 0
        for i in xrange(1, n - 1):
            i_mirror = 2 * C - i  # 等于i' = C - (i-C)
            P[i] = min(R - i, P[i_mirror]) if R > i else 0

            # 尝试扩展中心为i的回文
            while T[i + 1 + P[i]] == T[i - 1 - P[i]]:
                P[i] += 1

            # 如果中心为i的回文超越了R，根据已扩展的回文来调整中心
            if i + P[i] > R:
                C = i
                R = i + P[i]

        # 找出P中的最大值
        maxLen = 0
        centerIndex = 0

        for i in xrange(n):
            if P[i] > maxLen:
                maxLen = P[i]
                centerIndex = i
        # print maxLen, centerIndex
        # print (centerIndex - 1 - maxLen) / 2, (centerIndex - 1 - maxLen) / 2 + maxLen
        return s[(centerIndex - 1 - maxLen) / 2: (centerIndex - 1 - maxLen) / 2 + maxLen]

    def preProcess(self, s):
        n = len(s)
        if n == 0:
            return "^$"
        ret = "^"
        for i in xrange(n):
            ret += "#" + s[i]

        ret += "#$"
        return ret


if __name__ == '__main__':
    s = Solution()
    print s.longestPalindrome('ccd')